package site.wanjiahao.sort.compare;

import site.wanjiahao.sort.Sort;

import java.util.ArrayList;
import java.util.List;

public class ShellSort<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        List<Integer> stepSequence = getStepSequence();
        for (Integer step : stepSequence) {
            for (int i = step; i < array.length; i += step) {
                // 逆序对逐渐减少，使用插入排序
                E cur = array[i];
                int curIndex = i;
                while (curIndex >= step && cmp(cur, array[curIndex - step]) < 0) {
                    // 挪动元素
                    array[curIndex] = array[curIndex-=step];
                }
                array[curIndex] = cur;
            }
        }
    }

    // 获取步长序列
    protected List<Integer> getStepSequence() {
        ArrayList<Integer> list = new ArrayList<>();
        int len = array.length;
        int k = 1;
        int result;
        while ((result = (len >> k)) >= 1) {
            list.add(result);
            k++;
        }
        return list;
    }

}
